Skip to main content

第28章 字符串相关算法

字符串相关算法主要用于处理字符串的查找、替换、匹配等操作，在文本处理、数据解析、编程竞赛等场景中应用广泛。

28.1 字符串查找算法​

28.1.1 查找单个字符​

C语言实现​

#include <stdio.h>
int main()
{
    char str[] = "hello";
    char c = 'l';
    int pos = -1; // -1代表未找到
    for (int i = 0; str[i] != '\0'; i++)
    {
        if (str[i] == c)
        {
            pos = i;
            break;
        }
    }
    printf("字符'%c'第一次出现位置：%d\n", c, pos);
    return 0;
}

C++ string实现​

#include <iostream>
#include <string>
using namespace std;
int main()
{
    string str = "hello";
    char c = 'l';
    size_t pos = str.find(c);
    if (pos != string::npos)
    {
        cout << "字符'" << c << "'位置：" << pos << endl;
    }
    else
    {
        cout << "未找到该字符" << endl;
    }
    return 0;
}

28.1.2 暴力匹配查找子串​

思路：主串逐个起点与子串逐位对比，匹配失败则主串下标后移、子串重置。

#include <stdio.h>
#include <string.h>
int main()
{
    char str[] = "ababcabcd";
    char sub[] = "abc";
    int strLen = strlen(str);
    int subLen = strlen(sub);
    int pos = -1;
    for (int i = 0; i <= strLen - subLen; i++)
    {
        int j;
        for (j = 0; j < subLen; j++)
        {
            if (str[i + j] != sub[j])
                break;
        }
        if (j == subLen)
        {
            pos = i;
            break;
        }
    }
    printf("子串首次起始下标：%d\n", pos);
    return 0;
}

28.2 字符串替换算法​

将指定全部旧子串替换为新子串（C++ string）

#include <iostream>
#include <string>
using namespace std;
int main()
{
    string str = "hello world, world is great";
    string oldSub = "world";
    string newSub = "earth";
    size_t pos = 0;
    while ((pos = str.find(oldSub, pos)) != string::npos)
    {
        str.replace(pos, oldSub.length(), newSub);
        pos += newSub.length(); // 跳过已替换部分，防止重复匹配
    }
    cout << "替换后：" << str << endl;
    return 0;
}

28.3 字符串反转算法​

标准库reverse实现​

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
    string str = "reverse";
    reverse(str.begin(), str.end());
    cout << "反转结果：" << str << endl;
    return 0;
}

手动双指针反转字符数组​

#include <stdio.h>
#include <string.h>
int main()
{
    char str[] = "abc123";
    int len = strlen(str);
    int l = 0, r = len - 1;
    while (l < r)
    {
        char temp = str[l];
        str[l] = str[r];
        str[r] = temp;
        l++;
        r--;
    }
    printf("反转：%s\n", str);
    return 0;
}

28.4 字符串分割算法​

按分隔符拆分字符串，存储到字符串数组

#include <iostream>
#include <string>
using namespace std;
int main()
{
    string str = "apple, banana, orange";
    char delim = ',';
    const int MAX_PARTS = 10;
    string parts[MAX_PARTS];
    int partCnt = 0;
    string cur;
    for (char ch : str)
    {
        if (ch == delim)
        {
            if (!cur.empty() && partCnt < MAX_PARTS)
            {
                parts[partCnt++] = cur;
                cur.clear();
            }
        }
        else
        {
            cur += ch;
        }
    }
    // 存入最后一段子串
    if (!cur.empty() && partCnt < MAX_PARTS)
        parts[partCnt++] = cur;
    cout << "分割结果共" << partCnt << "段：" << endl;
    for (int i = 0; i < partCnt; i++)
        cout << i + 1 << "：" << parts[i] << endl;
    return 0;
}

28.5 字符串去空格​

去除全部空格（C字符数组）​

#include <stdio.h>
#include <string.h>
int main()
{
    char str[] = "h e l l o  w o r l d";
    int j = 0;
    for (int i = 0; str[i] != '\0'; i++)
    {
        if (str[i] != ' ')
            str[j++] = str[i];
    }
    str[j] = '\0';
    printf("去除所有空格：%s\n", str);
    return 0;
}

仅去除首尾空格​

#include <stdio.h>
#include <string.h>
int main()
{
    char str2[] = "  hello world  ";
    int len = strlen(str2);
    int start = 0, end = len - 1;
    // 找到第一个非空格
    while (start <= end && str2[start] == '')
        start++;
    // 找到最后一个非空格
    while (end >= start && str2[end] == ' ')
        end--;
    // 前移覆盖前导空格
    int k = 0;
    for (; start <= end; k++, start++)
        str2[k] = str2[start];
    str2[k] = '\0';
    printf("去除首尾空格：%s\n", str2);
    return 0;
}

28.6 大小写转换（简述）​

字符c：

  • 转大写：c - 32（小写a-z：97122，大写A-Z：6590）
  • 转小写：c + 32
char ch = 'a';
ch -= 32; // 'A'